{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Weighted Subgraph With the Required Paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #shortest-path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #最短路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumWeight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得到要求路径的最小带权子图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;，它表示一个 <strong>带权有向</strong> 图的节点数，节点编号为&nbsp;<code>0</code> 到&nbsp;<code>n - 1</code>&nbsp;。</p>\n",
    "\n",
    "<p>同时给你一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [from<sub>i</sub>, to<sub>i</sub>, weight<sub>i</sub>]</code>&nbsp;，表示从&nbsp;<code>from<sub>i</sub></code>&nbsp;到&nbsp;<code>to<sub>i</sub></code>&nbsp;有一条边权为&nbsp;<code>weight<sub>i</sub></code>&nbsp;的 <strong>有向</strong> 边。</p>\n",
    "\n",
    "<p>最后，给你三个 <strong>互不相同</strong>&nbsp;的整数&nbsp;<code>src1</code>&nbsp;，<code>src2</code>&nbsp;和&nbsp;<code>dest</code>&nbsp;，表示图中三个不同的点。</p>\n",
    "\n",
    "<p>请你从图中选出一个 <b>边权和最小</b>&nbsp;的子图，使得从 <code>src1</code>&nbsp;和 <code>src2</code>&nbsp;出发，在这个子图中，都 <strong>可以</strong>&nbsp;到达 <code>dest</code>&nbsp;。如果这样的子图不存在，请返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>子图</strong>&nbsp;中的点和边都应该属于原图的一部分。子图的边权和定义为它所包含的所有边的权值之和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/02/17/example1drawio.png\" style=\"width: 263px; height: 250px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5\n",
    "<b>输出：</b>9\n",
    "<strong>解释：</strong>\n",
    "上图为输入的图。\n",
    "蓝色边为最优子图之一。\n",
    "注意，子图 [[1,0,3],[0,5,6]] 也能得到最优解，但无法在满足所有限制的前提下，得到更优解。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/02/17/example2-1drawio.png\" style=\"width: 350px; height: 51px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2\n",
    "<b>输出：</b>-1\n",
    "<strong>解释：</strong>\n",
    "上图为输入的图。\n",
    "可以看到，不存在从节点 1 到节点 2 的路径，所以不存在任何子图满足所有限制。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= from<sub>i</sub>, to<sub>i</sub>, src1, src2, dest &lt;= n - 1</code></li>\n",
    "\t<li><code>from<sub>i</sub> != to<sub>i</sub></code></li>\n",
    "\t<li><code>src1</code>&nbsp;，<code>src2</code>&nbsp;和&nbsp;<code>dest</code>&nbsp;两两不同。</li>\n",
    "\t<li><code>1 &lt;= weight[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-weighted-subgraph-with-the-required-paths](https://leetcode.cn/problems/minimum-weighted-subgraph-with-the-required-paths/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-weighted-subgraph-with-the-required-paths](https://leetcode.cn/problems/minimum-weighted-subgraph-with-the-required-paths/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]]\\n0\\n1\\n5', '3\\n[[0,1,1],[2,1,1]]\\n0\\n1\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 1. build adjacency list of directed graph and reversed directed graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        reversed_g = [[] for _ in range(n)]\n",
    "\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            reversed_g[v].append((u, w))\n",
    "\n",
    "        # 2. SPFA\n",
    "        src1To = self.SPFA(src1, g, n)\n",
    "        src2To = self.SPFA(src2, g, n)\n",
    "        destTo = self.SPFA(dest, reversed_g, n)\n",
    "\n",
    "        # 3. find min distance\n",
    "        ans = min(sum(d) for d in zip(src1To, src2To, destTo))\n",
    "\n",
    "        return ans if ans < math.inf else -1\n",
    "\n",
    "    def SPFA(self, s: int, g: List[List[int]], n: int) -> List[int]:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist[v] > (d := dist[u] + w):\n",
    "                dist[v] = d \n",
    "                if not in_queue[v]:\n",
    "                    queue.append(v)\n",
    "                    in_queue[v] = True\n",
    "\n",
    "        dist = [math.inf] * n \n",
    "        dist[s] = 0\n",
    "        \n",
    "        in_queue = [False] * n\n",
    "        queue = deque([s])\n",
    "        in_queue[s] = True\n",
    "        while queue:\n",
    "            u = queue.popleft()\n",
    "            in_queue[u] = False \n",
    "\n",
    "            for v, w in g[u]:\n",
    "                relax(u, v, w)\n",
    "        \n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 从dest出发到src1和src2\n",
    "        # dis[i] 代表到i的最短路\n",
    "        # 计算des -> node, node -> src1, node -> src2\n",
    "        # cost(des->node) + cost(src1->node) + cost(src2->node)\n",
    "\n",
    "        # 返回从start开始到所有其他点的最短路径\n",
    "        def calculateDistance(n, g, start):\n",
    "            # 使用SPFA(Shortest Path Faster Algorithm)\n",
    "            dis = [inf] * n\n",
    "            in_dq = [False] * n\n",
    "            dis[start] = 0\n",
    "            dq = collections.deque([start])\n",
    "\n",
    "            while dq:\n",
    "                u = dq.popleft()\n",
    "                in_dq[u] = False\n",
    "                \n",
    "                for v, cost in g[u]:\n",
    "                    if dis[v] > dis[u] + cost:\n",
    "                        dis[v] = dis[u] + cost\n",
    "                        if not in_dq[v]:\n",
    "                            dq.append(v)\n",
    "                            in_dq[v] = True\n",
    "            \n",
    "            return dis\n",
    "\n",
    "        \n",
    "        graph, graph_reverse = [[] for _ in range(n)], [[] for _ in range(n)]\n",
    "        for start, end, cost in edges:\n",
    "            graph[start].append((end, cost))\n",
    "            graph_reverse[end].append((start, cost))\n",
    "        dis_dest = calculateDistance(n, graph_reverse, dest)\n",
    "        dis_src1 = calculateDistance(n, graph, src1)\n",
    "        dis_src2 = calculateDistance(n, graph, src2)\n",
    "        ans = inf\n",
    "        # for i in range(n):\n",
    "        #     ans = min(ans, dis_dest[i] + dis_src1[i] + dis_src2[i])\n",
    "        ans = min(sum(d) for d in zip(dis_dest, dis_src1, dis_src2))\n",
    "        return ans if ans != inf else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 1. build adjacency list of directed graph and reversed directed graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        reversed_g = [[] for _ in range(n)]\n",
    "\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            reversed_g[v].append((u, w))\n",
    "\n",
    "        # 2. heap-optimized Dijkstra\n",
    "        src1To = self.Dijkstra(src1, g, n)\n",
    "        src2To = self.Dijkstra(src2, g, n)\n",
    "        destTo = self.Dijkstra(dest, reversed_g, n)\n",
    "\n",
    "        # 3. find min distance\n",
    "        ans = min(sum(d) for d in zip(src1To, src2To, destTo))\n",
    "\n",
    "        return ans if ans < math.inf else -1\n",
    "\n",
    "    def Dijkstra(self, s: int, g: List[List[int]], n: int) -> List[int]:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist[v] > (d := dist[u] + w):\n",
    "                dist[v] = d \n",
    "                heapq.heappush(pq, (d, v))\n",
    "\n",
    "        dist = [math.inf] * n \n",
    "        dist[s] = 0\n",
    "        \n",
    "        pq = [(0, s)]\n",
    "        while pq:\n",
    "            d, u = heapq.heappop(pq)\n",
    "            if d <= dist[u]:\n",
    "                for v, w in g[u]:\n",
    "                    relax(u, v, w)\n",
    "            \n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        def dijkstra(g : List[List[tuple]], start: int) -> List[int]:\n",
    "            dis = [inf] * n\n",
    "            dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "            while pq:\n",
    "                d, x = heappop(pq)\n",
    "                if d > dis[x] :\n",
    "                    continue\n",
    "                for y, w in g[x]:\n",
    "                    newd = dis[x] + w\n",
    "                    if newd < dis[y]:\n",
    "                        dis[y ] = newd\n",
    "                        heappush(pq, (newd, y))\n",
    "            return dis\n",
    "\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y, w in edges:\n",
    "            g[x].append((y, w))\n",
    "            rg[y].append((x, w))\n",
    "        \n",
    "        d1 = dijkstra(g, src1)\n",
    "        d2 = dijkstra(g, src2)\n",
    "        d3 = dijkstra(rg, dest)\n",
    "\n",
    "        ans = min(sum(d) for d in zip(d1, d2, d3))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from heapq import heappop, heappush\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        def dijkstra(g: List[List[tuple]], start: int) -> List[int]:\n",
    "            dis = [inf] * n\n",
    "            dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "            while pq:\n",
    "                d, x = heappop(pq)\n",
    "                if d > dis[x]:\n",
    "                    continue\n",
    "                for y, wt in g[x]:\n",
    "                    new_d = dis[x] + wt\n",
    "                    if new_d < dis[y]:\n",
    "                        dis[y] = new_d\n",
    "                        heappush(pq, (new_d, y))\n",
    "            return dis\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y, wt in edges:\n",
    "            g[x].append((y, wt))\n",
    "            rg[y].append((x, wt))\n",
    "\n",
    "        d1 = dijkstra(g, src1)\n",
    "        d2 = dijkstra(g, src2)\n",
    "        d3 = dijkstra(rg, dest)\n",
    "\n",
    "        ans = min(sum(d) for d in zip(d1, d2, d3))\n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        #需要注意的是还原路径,以及避免重复统计\n",
    "        #多种选择使得贪心难以还原\n",
    "\n",
    "        #横看成岭侧成峰，我们先看看怎么求出边权和\n",
    "        #边权和还是很难求，由易到难的，我们可以枚举交汇点判断\n",
    "\n",
    "        def dijsktra(g,start):\n",
    "            dist=[inf]*n\n",
    "            dist[start]=0\n",
    "            h=[(0,start)]\n",
    "            while h:\n",
    "                d,x=heappop(h)\n",
    "                if d>dist[x]:continue \n",
    "                for y,w in g[x]:\n",
    "                    if d+w<dist[y]:\n",
    "                        dist[y]=d+w\n",
    "                        heappush(h,(dist[y],y))\n",
    "            return dist\n",
    "\n",
    "\n",
    "        g=[[]*n for _ in range(n)]\n",
    "        rg=[[]*n for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w))\n",
    "            rg[y].append((x,w))\n",
    "        d1=dijsktra(g, src1)\n",
    "        d2=dijsktra(g, src2)\n",
    "        d3=dijsktra(rg, dest)\n",
    "        ans=min(d1[x]+d2[x]+d3[x] for x in range(n))\n",
    "        return ans if ans<inf else -1\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\r\n",
    "        def dijkstra(g: List[List[tuple]], start: int) -> List[int]:\r\n",
    "            dis = [inf] * n\r\n",
    "            dis[start] = 0\r\n",
    "            pq = [(0, start)]\r\n",
    "            while pq:\r\n",
    "                d, x = heappop(pq)\r\n",
    "                if d > dis[x]:\r\n",
    "                    continue\r\n",
    "                for y, wt in g[x]:\r\n",
    "                    new_d = dis[x] + wt\r\n",
    "                    if new_d < dis[y]:\r\n",
    "                        dis[y] = new_d\r\n",
    "                        heappush(pq, (new_d, y))\r\n",
    "            return dis\r\n",
    "\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        rg = [[] for _ in range(n)]\r\n",
    "        for x, y, wt in edges:\r\n",
    "            g[x].append((y, wt))\r\n",
    "            rg[y].append((x, wt))\r\n",
    "\r\n",
    "        d1 = dijkstra(g, src1)\r\n",
    "        d2 = dijkstra(g, src2)\r\n",
    "        d3 = dijkstra(rg, dest)\r\n",
    "\r\n",
    "        ans = min(sum(d) for d in zip(d1, d2, d3))\r\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 1. build adjacency list of directed graph and reversed directed graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        reversed_g = [[] for _ in range(n)]\n",
    "\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            reversed_g[v].append((u, w))\n",
    "\n",
    "        # 2. SPFA\n",
    "        src1To = self.SPFA(src1, g, n)\n",
    "        src2To = self.SPFA(src2, g, n)\n",
    "        destTo = self.SPFA(dest, reversed_g, n)\n",
    "\n",
    "        # 3. find min distance\n",
    "        ans = min(sum(d) for d in zip(src1To, src2To, destTo))\n",
    "\n",
    "        return ans if ans < math.inf else -1\n",
    "\n",
    "    def SPFA(self, s: int, g: List[List[int]], n: int) -> List[int]:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist[v] > (d := dist[u] + w):\n",
    "                dist[v] = d \n",
    "                if not in_queue[v]:\n",
    "                    queue.append(v)\n",
    "                    in_queue[v] = True\n",
    "\n",
    "        dist = [math.inf] * n \n",
    "        dist[s] = 0\n",
    "        \n",
    "        in_queue = [False] * n\n",
    "        queue = deque([s])\n",
    "        in_queue[s] = True\n",
    "        while queue:\n",
    "            u = queue.popleft()\n",
    "            in_queue[u] = False \n",
    "\n",
    "            for v, w in g[u]:\n",
    "                relax(u, v, w)\n",
    "        \n",
    "        return dist\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            rg[v].append((u, w))\n",
    "        \n",
    "        def dij(g, s):\n",
    "            dis = [inf] * n\n",
    "            dis[s] = 0\n",
    "            q = [(0, s)]\n",
    "            while q:\n",
    "                d, x = heappop(q)\n",
    "                if dis[x] < d: continue\n",
    "                for y, w in g[x]:\n",
    "                    nd = d + w\n",
    "                    if nd < dis[y]:\n",
    "                        dis[y] = nd\n",
    "                        heappush(q, (nd, y))\n",
    "            return dis\n",
    "        \n",
    "        d1 = dij(g, src1)\n",
    "        d2 = dij(g, src2)\n",
    "        d3 = dij(rg, dest)\n",
    "        \n",
    "        ans = min(sum(d) for d in zip(d1, d2, d3))\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        def dijkstra(g: List[List[tuple]], start: int) -> List[int]:\n",
    "            dis = [inf] * n\n",
    "            dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "            while pq:\n",
    "                d, x = heappop(pq)\n",
    "                if d > dis[x]:\n",
    "                    continue\n",
    "                for y, wt in g[x]:\n",
    "                    new_d = dis[x] + wt\n",
    "                    if new_d < dis[y]:\n",
    "                        dis[y] = new_d\n",
    "                        heappush(pq, (new_d, y))\n",
    "            return dis\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y, wt in edges:\n",
    "            g[x].append((y, wt))\n",
    "            rg[y].append((x, wt))\n",
    "\n",
    "        d1 = dijkstra(g, src1)\n",
    "        d2 = dijkstra(g, src2)\n",
    "        d3 = dijkstra(rg, dest)\n",
    "\n",
    "        ans = min(sum(d) for d in zip(d1, d2, d3))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        def dijstra(g, start):\n",
    "            d = [inf] * n\n",
    "            d[start] = 0\n",
    "            q = [(start, 0)]\n",
    "            while q:\n",
    "                x, val = heappop(q)\n",
    "                if d[x] < val:\n",
    "                    continue\n",
    "                for y, weight in g[x]:\n",
    "                    new_d = d[x] + weight\n",
    "                    if new_d < d[y]:\n",
    "                        d[y] = new_d\n",
    "                        heappush(q, (y, new_d)) \n",
    "            return d\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y, weight in edges:\n",
    "            g[x].append((y, weight))\n",
    "            rg[y].append((x, weight))\n",
    "        d1 = dijstra(g, src1)\n",
    "        d2 = dijstra(g, src2)\n",
    "        d3 = dijstra(rg, dest)\n",
    "        ans = min(sum([d11,d22, d33]) for d11, d22, d33 in zip(d1, d2, d3))\n",
    "        # ans = min((sum(d) for d in zip(d1, d2, d3)))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        def dijkstra(g: List[List[tuple]], start: int) -> List[int]:\n",
    "            dis = [inf] * n\n",
    "            dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "            while pq:\n",
    "                d, x = heappop(pq)\n",
    "                if d > dis[x]:\n",
    "                    continue\n",
    "                for y, wt in g[x]:\n",
    "                    new_d = dis[x] + wt\n",
    "                    if new_d < dis[y]:\n",
    "                        dis[y] = new_d\n",
    "                        heappush(pq, (new_d, y))\n",
    "            return dis\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y, wt in edges:\n",
    "            g[x].append((y, wt))\n",
    "            rg[y].append((x, wt))\n",
    "\n",
    "        d1 = dijkstra(g, src1)\n",
    "        d2 = dijkstra(g, src2)\n",
    "        d3 = dijkstra(rg, dest)\n",
    "\n",
    "        ans = min(sum(d) for d in zip(d1, d2, d3))\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        def dijkstra(g: List[List[tuple]], start: int) -> List[int]:\n",
    "            dis = [inf] * n\n",
    "            dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "            while pq:\n",
    "                d, x = heappop(pq)\n",
    "                if d > dis[x]:\n",
    "                    continue\n",
    "                for y, wt in g[x]:\n",
    "                    new_d = dis[x] + wt\n",
    "                    if new_d < dis[y]:\n",
    "                        dis[y] = new_d\n",
    "                        heappush(pq, (new_d, y))\n",
    "            return dis\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y, wt in edges:\n",
    "            g[x].append((y, wt))\n",
    "            rg[y].append((x, wt))\n",
    "\n",
    "        d1 = dijkstra(g, src1)\n",
    "        d2 = dijkstra(g, src2)\n",
    "        d3 = dijkstra(rg, dest)\n",
    "\n",
    "        ans = min(sum(d) for d in zip(d1, d2, d3))\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        def dijkstra(g: List[List[tuple]], start: int) -> List[int]:\n",
    "            dis = [inf] * n\n",
    "            dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "            while pq:\n",
    "                d, x = heappop(pq)\n",
    "                if d > dis[x]:\n",
    "                    continue\n",
    "                for y, wt in g[x]:\n",
    "                    new_d = dis[x] + wt\n",
    "                    if new_d < dis[y]:\n",
    "                        dis[y] = new_d\n",
    "                        heappush(pq, (new_d, y))\n",
    "            return dis\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y, wt in edges:\n",
    "            g[x].append((y, wt))\n",
    "            rg[y].append((x, wt))\n",
    "\n",
    "        d1 = dijkstra(g, src1)\n",
    "        d2 = dijkstra(g, src2)\n",
    "        d3 = dijkstra(rg, dest)\n",
    "\n",
    "        ans = min(sum(d) for d in zip(d1, d2, d3))\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        def dijsktra(g, start):\n",
    "            dist = [inf] * n\n",
    "            dist[start] = 0\n",
    "            st = [False] * n\n",
    "            q = [(0, start)]\n",
    "            while q:\n",
    "                d, x = q.pop(0)\n",
    "                st[x] = False\n",
    "                for y, wt in g[x]:\n",
    "                    if dist[y] > dist[x] + wt:\n",
    "                        dist[y] = dist[x] + wt\n",
    "                        if st[y] == False:\n",
    "                            q.append((dist[y], y))\n",
    "                            st[y] = True\n",
    "                \n",
    "            return dist\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[]for _ in range(n)]\n",
    "        for x, y, wt in edges:\n",
    "            g[x].append((y, wt))\n",
    "            rg[y].append((x, wt))\n",
    "        d1 = dijsktra(g, src1)\n",
    "        d2 = dijsktra(g, src2)\n",
    "        d3 = dijsktra(rg, dest)\n",
    "\n",
    "        ans = min(sum(d) for d in zip(d1, d2, d3))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 从dest出发到src1和src2\n",
    "        # dis[i] 代表到i的最短路\n",
    "        # 计算des -> node, node -> src1, node -> src2\n",
    "        # cost(des->node) + cost(src1->node) + cost(src2->node)\n",
    "\n",
    "        # 返回从start开始到所有其他点的最短路径\n",
    "        def calculateDistance(n, g, start):\n",
    "            # 使用SPFA(Shortest Path Faster Algorithm)\n",
    "            dis = [inf] * n\n",
    "            in_dq = [False] * n\n",
    "            dis[start] = 0\n",
    "            dq = collections.deque([start])\n",
    "\n",
    "            while dq:\n",
    "                u = dq.popleft()\n",
    "                in_dq[u] = False\n",
    "                \n",
    "                for v, cost in g[u]:\n",
    "                    if dis[v] > dis[u] + cost:\n",
    "                        dis[v] = dis[u] + cost\n",
    "                        if not in_dq[v]:\n",
    "                            dq.append(v)\n",
    "                            in_dq[v] = True\n",
    "            \n",
    "            return dis\n",
    "\n",
    "        \n",
    "        graph, graph_reverse = [[] for _ in range(n)], [[] for _ in range(n)]\n",
    "        for start, end, cost in edges:\n",
    "            graph[start].append((end, cost))\n",
    "            graph_reverse[end].append((start, cost))\n",
    "        dis_dest = calculateDistance(n, graph_reverse, dest)\n",
    "        dis_src1 = calculateDistance(n, graph, src1)\n",
    "        dis_src2 = calculateDistance(n, graph, src2)\n",
    "        ans = inf\n",
    "        print(dis_dest)\n",
    "        print(dis_src1)\n",
    "        print(dis_src2)\n",
    "        # for i in range(n):\n",
    "        #     ans = min(ans, dis_dest[i] + dis_src1[i] + dis_src2[i])\n",
    "        ans = min(sum(d) for d in zip(dis_dest, dis_src1, dis_src2))\n",
    "        return ans if ans != inf else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 从dest出发到src1和src2\n",
    "        # dis[i] 代表到i的最短路\n",
    "        # 计算des -> node, node -> src1, node -> src2\n",
    "        # cost(des->node) + cost(src1->node) + cost(src2->node)\n",
    "\n",
    "        # 返回从start开始到所有其他点的最短路径\n",
    "        def calculateDistance(n, g, start):\n",
    "            dis = [inf] * n\n",
    "            visited = [False] * n\n",
    "            # dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "\n",
    "            while pq:\n",
    "                dis_u, u = heapq.heappop(pq)\n",
    "                if visited[u]:\n",
    "                    continue\n",
    "\n",
    "                visited[u] = True\n",
    "                dis[u] = dis_u\n",
    "                for v, cost in g[u]:\n",
    "                    if dis[v] > dis_u + cost:\n",
    "                        dis[v] = dis_u + cost\n",
    "                        heapq.heappush(pq, (dis_u + cost, v))\n",
    "            \n",
    "            return dis\n",
    "\n",
    "        \n",
    "        graph, graph_reverse = [[] for _ in range(n)], [[] for _ in range(n)]\n",
    "        for start, end, cost in edges:\n",
    "            graph[start].append((end, cost))\n",
    "            graph_reverse[end].append((start, cost))\n",
    "        dis_dest = calculateDistance(n, graph_reverse, dest)\n",
    "        dis_src1 = calculateDistance(n, graph, src1)\n",
    "        dis_src2 = calculateDistance(n, graph, src2)\n",
    "        ans = inf\n",
    "        print(dis_dest)\n",
    "        print(dis_src1)\n",
    "        print(dis_src2)\n",
    "        for i in range(n):\n",
    "            ans = min(ans, dis_dest[i] + dis_src1[i] + dis_src2[i])\n",
    "        \n",
    "        return ans if ans != inf else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 从dest出发到src1和src2\n",
    "        # dis[i] 代表到i的最短路\n",
    "        # 计算des -> node, node -> src1, node -> src2\n",
    "        # cost(des->node) + cost(src1->node) + cost(src2->node)\n",
    "\n",
    "        # 返回从start开始到所有其他点的最短路径\n",
    "        def calculateDistance(n, g, start):\n",
    "            dis = [inf] * n\n",
    "            visited = [False] * n\n",
    "            # dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "\n",
    "            while pq:\n",
    "                dis_u, u = heapq.heappop(pq)\n",
    "                if visited[u]:\n",
    "                    continue\n",
    "\n",
    "                visited[u] = True\n",
    "                dis[u] = dis_u\n",
    "                for v, cost in g[u]:\n",
    "                    if dis[v] > dis_u + cost:\n",
    "                        dis[v] = dis_u + cost\n",
    "                        heapq.heappush(pq, (dis_u + cost, v))\n",
    "            \n",
    "            return dis\n",
    "\n",
    "        \n",
    "        graph, graph_reverse = [[] for _ in range(n)], [[] for _ in range(n)]\n",
    "        for start, end, cost in edges:\n",
    "            graph[start].append((end, cost))\n",
    "            graph_reverse[end].append((start, cost))\n",
    "        dis_dest = calculateDistance(n, graph_reverse, dest)\n",
    "        dis_src1 = calculateDistance(n, graph, src1)\n",
    "        dis_src2 = calculateDistance(n, graph, src2)\n",
    "        ans = inf\n",
    "        print(dis_dest)\n",
    "        print(dis_src1)\n",
    "        print(dis_src2)\n",
    "        for i in range(n):\n",
    "            ans = min(ans, dis_dest[i] + dis_src1[i] + dis_src2[i])\n",
    "        \n",
    "        return ans if ans != inf else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 从dest出发到src1和src2\n",
    "        # dis[i] 代表到i的最短路\n",
    "        # 计算des -> node, node -> src1, node -> src2\n",
    "        # cost(des->node) + cost(src1->node) + cost(src2->node)\n",
    "\n",
    "        # 返回从start开始到所有其他点的最短路径\n",
    "        def calculateDistance(n, g, start):\n",
    "            dis = [inf] * n\n",
    "            visited = [False] * n\n",
    "            # dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "\n",
    "            while pq:\n",
    "                dis_u, u = heapq.heappop(pq)\n",
    "                if visited[u]:\n",
    "                    continue\n",
    "\n",
    "                visited[u] = True\n",
    "                dis[u] = dis_u\n",
    "                for v, cost in g[u]:\n",
    "                    if dis[v] > dis_u + cost:\n",
    "                        dis[v] = dis_u + cost\n",
    "                        heapq.heappush(pq, (dis_u + cost, v))\n",
    "            \n",
    "            return dis\n",
    "\n",
    "        \n",
    "        graph, graph_reverse = [[] for _ in range(n)], [[] for _ in range(n)]\n",
    "        for start, end, cost in edges:\n",
    "            graph[start].append((end, cost))\n",
    "            graph_reverse[end].append((start, cost))\n",
    "        dis_dest = calculateDistance(n, graph_reverse, dest)\n",
    "        dis_src1 = calculateDistance(n, graph, src1)\n",
    "        dis_src2 = calculateDistance(n, graph, src2)\n",
    "        ans = inf\n",
    "        print(dis_dest)\n",
    "        print(dis_src1)\n",
    "        print(dis_src2)\n",
    "        for i in range(n):\n",
    "            ans = min(ans, dis_dest[i] + dis_src1[i] + dis_src2[i])\n",
    "        \n",
    "        return ans if ans != inf else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 从dest出发到src1和src2\n",
    "        # dis[i] 代表到i的最短路\n",
    "        # 计算des -> node, node -> src1, node -> src2\n",
    "        # cost(des->node) + cost(src1->node) + cost(src2->node)\n",
    "\n",
    "        # 返回从start开始到所有其他点的最短路径\n",
    "        def calculateDistance(n, g, start):\n",
    "            dis = [inf] * n\n",
    "            visited = [False] * n\n",
    "            # dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "\n",
    "            while pq:\n",
    "                dis_u, u = heapq.heappop(pq)\n",
    "                if visited[u]:\n",
    "                    continue\n",
    "\n",
    "                visited[u] = True\n",
    "                dis[u] = dis_u\n",
    "                for v, cost in g[u]:\n",
    "                    if dis[v] > dis_u + cost:\n",
    "                        dis[v] = dis_u + cost\n",
    "                        heapq.heappush(pq, (dis_u + cost, v))\n",
    "            \n",
    "            return dis\n",
    "\n",
    "        \n",
    "        graph, graph_reverse = [[] for _ in range(n)], [[] for _ in range(n)]\n",
    "        for start, end, cost in edges:\n",
    "            graph[start].append((end, cost))\n",
    "            graph_reverse[end].append((start, cost))\n",
    "        dis_dest = calculateDistance(n, graph_reverse, dest)\n",
    "        dis_src1 = calculateDistance(n, graph, src1)\n",
    "        dis_src2 = calculateDistance(n, graph, src2)\n",
    "        ans = inf\n",
    "        print(dis_dest)\n",
    "        print(dis_src1)\n",
    "        print(dis_src2)\n",
    "        for i in range(n):\n",
    "            ans = min(ans, dis_dest[i] + dis_src1[i] + dis_src2[i])\n",
    "        \n",
    "        return ans if ans != inf else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # 从dest出发到src1和src2\n",
    "        # dis[i] 代表到i的最短路\n",
    "        # 计算des -> node, node -> src1, node -> src2\n",
    "        # cost(des->node) + cost(src1->node) + cost(src2->node)\n",
    "\n",
    "        # 返回从start开始到所有其他点的最短路径\n",
    "        def calculateDistance(n, g, start):\n",
    "            dis = [inf] * n\n",
    "            visited = [False] * n\n",
    "            # dis[start] = 0\n",
    "            pq = [(0, start)]\n",
    "\n",
    "            while pq:\n",
    "                dis_u, u = heapq.heappop(pq)\n",
    "                if visited[u]:\n",
    "                    continue\n",
    "\n",
    "                visited[u] = True\n",
    "                dis[u] = dis_u\n",
    "                for v, cost in g[u]:\n",
    "                    if dis[v] > dis_u + cost:\n",
    "                        dis[v] = dis_u + cost\n",
    "                        heapq.heappush(pq, (dis_u + cost, v))\n",
    "            \n",
    "            return dis\n",
    "\n",
    "        \n",
    "        graph, graph_reverse = [[] for _ in range(n)], [[] for _ in range(n)]\n",
    "        for start, end, cost in edges:\n",
    "            graph[start].append((end, cost))\n",
    "            graph_reverse[end].append((start, cost))\n",
    "        dis_dest = calculateDistance(n, graph_reverse, dest)\n",
    "        dis_src1 = calculateDistance(n, graph, src1)\n",
    "        dis_src2 = calculateDistance(n, graph, src2)\n",
    "        ans = inf\n",
    "        print(dis_dest)\n",
    "        print(dis_src1)\n",
    "        print(dis_src2)\n",
    "        # for i in range(n):\n",
    "        #     ans = min(ans, dis_dest[i] + dis_src1[i] + dis_src2[i])\n",
    "        ans = min(sum(d) for d in zip(dis_dest, dis_src1, dis_src2))\n",
    "        return ans if ans != inf else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        fa = [[] for _ in range(n)]\n",
    "        for a, b, c in edges:\n",
    "            g[a].append([b, c])\n",
    "            fa[b].append([a, c])\n",
    "\n",
    "        def sp(src, g):\n",
    "            q = [[0, src]]\n",
    "            dist = [inf] * n\n",
    "            dist[src] = 0\n",
    "\n",
    "            while q:\n",
    "                d, node = heappop(q)\n",
    "                if d > dist[node]:\n",
    "                    continue\n",
    "                for son, w in g[node]:\n",
    "                    if dist[son] > w + dist[node]:\n",
    "                        dist[son] = w + dist[node]\n",
    "                        heappush(q, [dist[son], son])\n",
    "            return dist\n",
    "\n",
    "        dist1 = sp(src1, g)\n",
    "        dist2 = sp(src2, g)\n",
    "        dist3 = sp(dest, fa)\n",
    "        ret = inf\n",
    "        for i in range(n):\n",
    "            if ret > dist1[i] + dist2[i] + dist3[i]:\n",
    "                ret = dist1[i] + dist2[i] + dist3[i]\n",
    "        return ret if ret < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_dijkstra_result(dct: List[List[int]], src: int) -> List[float]:\n",
    "        # 模板: Dijkstra求最短路，变成负数求可以求最长路（还是正权值）\n",
    "        n = len(dct)\n",
    "        dis = [inf]*n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        return dis\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        rev = [[] for _ in range(n)]\n",
    "        for i, j, w in edges:\n",
    "            dct[i].append([j, w])\n",
    "            rev[j].append([i, w])\n",
    "        dis1 = Dijkstra().get_dijkstra_result(dct, src1)\n",
    "        dis2 = Dijkstra().get_dijkstra_result(dct, src2)\n",
    "        dis3 = Dijkstra().get_dijkstra_result(rev, dest)\n",
    "        ans = min(dis1[i]+dis2[i]+dis3[i] for i in range(n))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "            \n",
    "        def dijkstra(start, graph):\n",
    "            dist = [100000000000 for _ in range(n)]\n",
    "            dist[start] = 0\n",
    "            queue = [[0, start]]\n",
    "            while queue:\n",
    "                cur_dist, cur = heappop(queue)\n",
    "                if cur_dist > dist[cur]:\n",
    "                    continue\n",
    "                for nxt, weight in graph[cur]:\n",
    "                    nxt_dist = cur_dist + weight\n",
    "                    if nxt_dist < dist[nxt]:\n",
    "                        dist[nxt] = nxt_dist\n",
    "                        heappush(queue, [nxt_dist, nxt])\n",
    "            return dist\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y, w in edges:\n",
    "            g[x].append([y, w])\n",
    "            rg[y].append([x, w])\n",
    "        dist1 = dijkstra(src1, g)\n",
    "        dist2 = dijkstra(src2, g)\n",
    "        dist3 = dijkstra(dest, rg)\n",
    "        min_dist = min(d1 + d2 + d3 for d1, d2, d3 in zip(dist1, dist2, dist3))\n",
    "        return min_dist if min_dist < 100000000000 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        dist0=[float('inf') for i in range(n)]\n",
    "        dist1=[float('inf') for i in range(n)]\n",
    "        dist2=[float('inf') for i in range(n)]\n",
    "        dist0[src1]=0\n",
    "        dist1[src2]=0\n",
    "        dist2[dest]=0\n",
    "        def dji(graph, node, dist):\n",
    "            pq=PriorityQueue()\n",
    "            pq.put((node, 0))\n",
    "            while not pq.empty():\n",
    "                (temp,dis)=pq.get()\n",
    "                if dis>dist[temp]:\n",
    "                    continue\n",
    "                for (new_node, w) in graph[temp]:\n",
    "                    d=w+dis\n",
    "                    if d<dist[new_node]:\n",
    "                        dist[new_node]=d\n",
    "                        pq.put((new_node, d))\n",
    "\n",
    "        gra=[[] for _ in range(n)]\n",
    "        gra_rev=[[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            gra[edge[0]].append((edge[1], edge[2]))\n",
    "            gra_rev[edge[1]].append((edge[0], edge[2]))\n",
    "        dji(gra, src1, dist0)\n",
    "        dji(gra, src2, dist1)\n",
    "        dji(gra_rev, dest, dist2)\n",
    "        ans=float('inf')\n",
    "        for i in range(n):\n",
    "            if dist0[i]==float('inf') or dist1[i]==float('inf') or dist2[i]==float('inf'):\n",
    "                continue\n",
    "            ans=min(ans, dist0[i]+dist1[i]+dist2[i])\n",
    "        if ans==float('inf'):\n",
    "            return -1\n",
    "        return ans\n",
    "\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        def dijkstra(g, u):\n",
    "            dist = [inf] * n\n",
    "            dist[u] = 0\n",
    "            q = [(0, u)]\n",
    "            while q:\n",
    "                d, u = heappop(q)\n",
    "                if d > dist[u]:\n",
    "                    continue\n",
    "                for v, w in g[u]:\n",
    "                    if dist[v] > dist[u] + w:\n",
    "                        dist[v] = dist[u] + w\n",
    "                        heappush(q, (dist[v], v))\n",
    "            return dist\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        rg = defaultdict(list)\n",
    "        for f, t, w in edges:\n",
    "            g[f].append((t, w))\n",
    "            rg[t].append((f, w))\n",
    "        d1 = dijkstra(g, src1)\n",
    "        d2 = dijkstra(g, src2)\n",
    "        d3 = dijkstra(rg, dest)\n",
    "        ans = min(sum(v) for v in zip(d1, d2, d3))\n",
    "        return -1 if ans >= inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(\n",
    "        self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int\n",
    "    ) -> int:\n",
    "        def dijkstra(g, u):\n",
    "            dist = [inf] * n\n",
    "            dist[u] = 0\n",
    "            q = [(0, u)]\n",
    "            while q:\n",
    "                d, u = heappop(q)\n",
    "                if d > dist[u]:\n",
    "                    continue\n",
    "                for v, w in g[u]:\n",
    "                    if dist[v] > dist[u] + w:\n",
    "                        dist[v] = dist[u] + w\n",
    "                        heappush(q, (dist[v], v))\n",
    "            return dist\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        rg = defaultdict(list)\n",
    "        for f, t, w in edges:\n",
    "            g[f].append((t, w))\n",
    "            rg[t].append((f, w))\n",
    "        d1 = dijkstra(g, src1)\n",
    "        d2 = dijkstra(g, src2)\n",
    "        d3 = dijkstra(rg, dest)\n",
    "        ans = min(sum(v) for v in zip(d1, d2, d3))\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        d_graph = [[] for _ in range(n)]\n",
    "        r_graph = [[] for _ in range(n)]\n",
    "        for f,t,w in edges:\n",
    "            d_graph[f].append([t,w])\n",
    "            r_graph[t].append([f,w])\n",
    "\n",
    "        def getDist(src, graph):\n",
    "            dist = [float('inf')]*n\n",
    "            dist[src] = 0\n",
    "            heap = []\n",
    "            heapq.heappush(heap, [0,src])\n",
    "            t_set = set()\n",
    "            while(heap):\n",
    "                d, u  = heapq.heappop(heap)\n",
    "                if(u in t_set):\n",
    "                    continue\n",
    "                t_set.add(u)\n",
    "                for v, w in graph[u]:\n",
    "                    if(d+w < dist[v]):\n",
    "                        dist[v] = d+w \n",
    "                        heapq.heappush(heap, [dist[v], v])\n",
    "            return dist\n",
    "        dist1 = getDist(src1, d_graph)\n",
    "        dist2 = getDist(src2, d_graph)\n",
    "        dist_dest = getDist(dest, r_graph)\n",
    "        result = float('inf')\n",
    "        for c in range(n):\n",
    "            result = min(result, dist1[c] + dist2[c] + dist_dest[c])\n",
    "        return result if result < float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        d_graph = [[] for _ in range(n)]\n",
    "        r_graph = [[] for _ in range(n)]\n",
    "        for f,t,w in edges:\n",
    "            d_graph[f].append([t,w])\n",
    "            r_graph[t].append([f,w])\n",
    "\n",
    "        def getDist(src, graph):\n",
    "            dist = [float('inf')]*n\n",
    "            dist[src] = 0\n",
    "            heap = []\n",
    "            heapq.heappush(heap, [0,src])\n",
    "            t_set = set()\n",
    "            while(heap):\n",
    "                d, u  = heapq.heappop(heap)\n",
    "                if(u in t_set):\n",
    "                    continue\n",
    "                t_set.add(u)\n",
    "                for v, w in graph[u]:\n",
    "                    if(d+w < dist[v]):\n",
    "                        dist[v] = d+w \n",
    "                        heapq.heappush(heap, [dist[v], v])\n",
    "            return dist\n",
    "        dist1 = getDist(src1, d_graph)\n",
    "        dist2 = getDist(src2, d_graph)\n",
    "        dist_dest = getDist(dest, r_graph)\n",
    "        result = float('inf')\n",
    "        for c in range(n):\n",
    "            result = min(result, dist1[c] + dist2[c] + dist_dest[c])\n",
    "        return result if result < float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        g =defaultdict(list)\n",
    "        gr = defaultdict(list)\n",
    "        for a, b,w in edges:\n",
    "            g[a].append((b,w))\n",
    "            gr[b].append((a, w))\n",
    "        \n",
    "        def dijkstra(s, dist, graph):\n",
    "            vis = [0] * n \n",
    "            dist[s] = 0\n",
    "            Q = [(dist[s], s)]\n",
    "            while Q:\n",
    "                d, u = heapq.heappop(Q)\n",
    "                if vis[u]:\n",
    "                    continue \n",
    "                vis[u] = 1\n",
    "                for v,w in graph[u]:\n",
    "                    if dist[v] > dist[u] + w:\n",
    "                        dist[v] = dist[u] + w \n",
    "                        heapq.heappush(Q,(dist[v], v))\n",
    "        \n",
    "        dist1 = [float('inf')] * n \n",
    "        dist2 = [float('inf')] * n \n",
    "        dist3 = [float('inf')] * n \n",
    "        dijkstra(src1, dist1, g)\n",
    "        dijkstra(src2, dist2, g)\n",
    "        dijkstra(dest, dist3, gr)\n",
    "\n",
    "        ans= float('inf')\n",
    "        for t in range(n):\n",
    "            if dist1[t] != float('inf') and dist2[t] != float('inf') and dist3[t] != float('inf'):\n",
    "                ans = min(ans, dist1[t] + dist2[t] + dist3[t])\n",
    "        return ans if ans < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        inf = float('inf')\n",
    "        def st(s, edges):\n",
    "            dists = [inf]*n\n",
    "            h = [[0, s]]\n",
    "            while h:\n",
    "                d, s = heappop(h)\n",
    "                if dists[s] > d:\n",
    "                    dists[s] = d\n",
    "                    for w, _, t in edges[s]:\n",
    "                        heappush(h, [d+w, t])\n",
    "            return dists\n",
    "        posEdges = defaultdict(list)\n",
    "        revEdges = defaultdict(list)\n",
    "        for f, t, w in edges:\n",
    "            posEdges[f].append((w, f, t))\n",
    "            revEdges[t].append((w, t, f))\n",
    "        src1Dists = st(src1, posEdges)\n",
    "        src2Dists = st(src2, posEdges)\n",
    "        destDists = st(dest, revEdges)\n",
    "\n",
    "        res = min(min(src1Dists[x] + src2Dists[x] + destDists[x] for x in range(n)),\n",
    "            src1Dists[dest] + src2Dists[dest]\n",
    "        )\n",
    "        return res if res != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        rg = defaultdict(list)\n",
    "\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            rg[b].append((a, w))\n",
    "\n",
    "        # print(g)\n",
    "\n",
    "        def dijkstra(g, i):\n",
    "            q = [(0, i)]\n",
    "            dists = [inf] * n\n",
    "\n",
    "            while q:\n",
    "                d, x = heappop(q)\n",
    "                # print(d, x, dists, q)\n",
    "\n",
    "                if dists[x] > d:\n",
    "                    dists[x] = d\n",
    "                else:\n",
    "                    continue\n",
    "\n",
    "                for y, w in g[x]:\n",
    "                    nd = w + d\n",
    "\n",
    "                    if nd < dists[y]:\n",
    "                        heappush(q, (nd, y))\n",
    "\n",
    "            return dists\n",
    "\n",
    "        ret = inf\n",
    "        d1 = dijkstra(g, src1)\n",
    "        d2 = dijkstra(g, src2)\n",
    "        d3 = dijkstra(rg, dest)\n",
    "\n",
    "        for k in range(n):\n",
    "            ret = min(ret, d1[k] + d2[k] + d3[k])\n",
    "\n",
    "        return ret if ret != inf else -1\n",
    "\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        rg = defaultdict(list)\n",
    "        \n",
    "        def dijkstra(graph, start):\n",
    "            dist = [float('inf')]*n\n",
    "            dist[start] = 0\n",
    "            queue = [(0,start)]\n",
    "            while queue:\n",
    "                dis,x = heapq.heappop(queue)\n",
    "                if dist[x]<dis:\n",
    "                    continue\n",
    "                for nextN,nextD in graph[x]:\n",
    "                    if dis+nextD<dist[nextN]:\n",
    "                        dist[nextN] = dis+nextD\n",
    "                        heapq.heappush(queue, (dist[nextN],nextN))\n",
    "                pass\n",
    "            return dist\n",
    "\n",
    "        for u,v,w in edges:\n",
    "            g[u].append((v,w))\n",
    "            rg[v].append((u,w))\n",
    "        \n",
    "        dist1 = dijkstra(g, src1)\n",
    "        dist2 = dijkstra(g, src2)\n",
    "        distd = dijkstra(rg, dest)\n",
    "        \n",
    "        min_sum = 10**10+1\n",
    "        for d in zip(dist1,dist2,distd):\n",
    "            min_sum = min(min_sum, sum(d))\n",
    "        return min_sum if min_sum!=10**10+1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        G = defaultdict(list)\n",
    "        for a,b,v in edges:\n",
    "            G[a].append((b,v))\n",
    "        revG = defaultdict(list)\n",
    "        for a,b,v in edges:\n",
    "            revG[b].append((a,v))\n",
    "        res = inf\n",
    "        def f(s):\n",
    "            dis = [inf] * n;\n",
    "            q = [(0,s)]\n",
    "            while q:\n",
    "                v,o = heappop(q)\n",
    "                if dis[o] != inf:continue\n",
    "                dis[o] = v\n",
    "                for nxt,nv in G[o]:\n",
    "                    if dis[nxt] != inf:continue\n",
    "                    heappush(q,(v+nv,nxt))\n",
    "            return dis\n",
    "        def ff(s):\n",
    "            dis = [inf] * n;\n",
    "            q = [(0,s)]\n",
    "            while q:\n",
    "                v,o = heappop(q)\n",
    "                if dis[o] != inf:continue\n",
    "                dis[o] = v\n",
    "                for nxt,nv in revG[o]:\n",
    "                    if dis[nxt] != inf:continue\n",
    "                    heappush(q,(v+nv,nxt))\n",
    "            return dis\n",
    "        s1,s2,d = src1,src2,dest\n",
    "        DIS1 = f(s1)\n",
    "        DIS2 = f(s2)\n",
    "        DISd = ff(d)\n",
    "        res = min([a+b+c for a,b,c in zip(DIS1,DIS2,DISd)])\n",
    "        return res if res < inf else -1\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heapify, heappop, heappush\r\n",
    "maxWeight = 100000000000\r\n",
    "def dijstra(conn: list[dict[int, int]], src: int, n: int):\r\n",
    "    dist = [maxWeight] * n\r\n",
    "    dist[src] = 0\r\n",
    "    dij = [(0, src)]\r\n",
    "    heapify(dij)\r\n",
    "    while dij:\r\n",
    "        d, node = heappop(dij)\r\n",
    "        if d > dist[node]: continue\r\n",
    "        for nxt, w in conn[node].items():\r\n",
    "            if d + w < dist[nxt]:\r\n",
    "                dist[nxt] = d + w\r\n",
    "                heappush(dij, (d + w, nxt))\r\n",
    "    yield from dist\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\r\n",
    "        conn: list[dict[int, int]] = [dict() for _ in range(n)]\r\n",
    "        conn_rev: list[dict[int, int]] = [dict() for _ in range(n)]\r\n",
    "        for u, v, w in edges:\r\n",
    "            conn[u].setdefault(v, maxWeight)\r\n",
    "            conn_rev[v].setdefault(u, maxWeight)\r\n",
    "            conn[u][v] = min(conn[u][v], w)\r\n",
    "            conn_rev[v][u] = min(conn_rev[v][u], w)\r\n",
    "        \r\n",
    "        res = min(a + b + c for a, b, c in zip(dijstra(conn, src1, n), dijstra(conn, src2, n), dijstra(conn_rev, dest, n)))\r\n",
    "        return -1 if res >= maxWeight else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import collections\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        e=collections.defaultdict(list)\n",
    "        re=collections.defaultdict(list)\n",
    "        for i,j,k in edges:\n",
    "            e[i].append([j,k])\n",
    "            re[j].append([i,k])\n",
    "        l=[]\n",
    "        def dijkstra(st,co):\n",
    "            dis=[float(\"inf\")]*n\n",
    "            l=[]\n",
    "            heapq.heappush(l,[0,st])\n",
    "            while l:\n",
    "                d,now=heapq.heappop(l)\n",
    "                print(dis[now],d,now)\n",
    "                if dis[now]>d:\n",
    "                    dis[now]=d \n",
    "                else:\n",
    "                    continue\n",
    "                for a,d2 in co[now]:\n",
    "                    if d+d2<dis[a]:\n",
    "                        heapq.heappush(l,[d2+d,a])\n",
    "            return dis \n",
    "        dis1=dijkstra(src1,e)\n",
    "        dis2=dijkstra(src2,e)\n",
    "        dis3=dijkstra(dest,re)\n",
    "        print(dis1,dis2,dis3)\n",
    "        ans=float(\"inf\")\n",
    "        for i in range(n):\n",
    "            dd=dis1[i]+dis2[i]+dis3[i]\n",
    "            ans=min(dd,ans)\n",
    "        if ans==float(\"inf\"):\n",
    "            ans=-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        import heapq\n",
    "\n",
    "        isconnect = collections.defaultdict(list)\n",
    "        outconnect = collections.defaultdict(list)\n",
    "        for s,e,w in edges:\n",
    "            isconnect[s].append((e,w))\n",
    "            outconnect[e].append((s,w))\n",
    "        def djistra(ori, graph):\n",
    "            dis= [float('inf')]*n\n",
    "            dis[ori] = 0\n",
    "            queue = [(0,ori)]\n",
    "            visited = set()\n",
    "            while queue:\n",
    "                d, p = heapq.heappop(queue) \n",
    "                if p in visited:\n",
    "                    continue\n",
    "                dis[p]=d\n",
    "                visited.add(p)\n",
    "                for i,dd in graph[p]:\n",
    "                    if i not in visited:\n",
    "                        heapq.heappush(queue, (d+dd, i))\n",
    "            return dis[:]\n",
    "\n",
    "        dis1 = djistra(src1, isconnect)\n",
    "        dis2 = djistra(src2, isconnect)\n",
    "        anti_dis = djistra(dest, outconnect)\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            if dis1[i]!=float('inf') and dis2[i]!=float('inf') and anti_dis[i]!=float('inf'):\n",
    "                res = min(dis1[i]+dis2[i]+anti_dis[i], res)\n",
    "        \n",
    "        return -1 if res==float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        g, grev = defaultdict(list), defaultdict(list)\n",
    "        for (x, y, z) in edges:\n",
    "            g[x].append((y, z))\n",
    "            grev[y].append((x, z))\n",
    "\n",
    "        def dijkstra(graph:Dict[int, List[int]], start:int)-> List[int]:\n",
    "            dist = [-1] * n\n",
    "            dist[start] = 0\n",
    "            used = set()\n",
    "            q = [(0, start)]\n",
    "\n",
    "            while q:\n",
    "                u = heapq.heappop(q)[1]\n",
    "                if u in used:\n",
    "                    continue\n",
    "                used.add(u)\n",
    "\n",
    "                for (v, weight) in graph[u]:\n",
    "                    target = dist[u] + weight\n",
    "                    if dist[v] == -1 or target < dist[v]:\n",
    "                        dist[v] = target\n",
    "                        heapq.heappush(q, (dist[v], v))\n",
    "            return dist\n",
    "\n",
    "        dist1, dist2, dist3 = dijkstra(g, src1), dijkstra(g, src2), dijkstra(grev, dest)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dist1[i] != -1 and dist2[i] != -1 and dist3[i] != -1:\n",
    "                result = dist1[i] + dist2[i] + dist3[i]\n",
    "                if ans == -1 or result < ans:\n",
    "                    ans = result\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        # graph = [[float('inf')]*n for _ in range(n)]\n",
    "        # graph_re = [[float('inf')]*n for _ in range(n)]\n",
    "        # for u,v,w in edges:\n",
    "        #     #print(u,v,w)\n",
    "        #     if w < graph[u][v]:\n",
    "        #         graph[u][v] = w\n",
    "        #     if w < graph_re[v][u]:\n",
    "        #         graph_re[v][u] = w\n",
    "        # #print(graph)\n",
    "        # #print('11111')\n",
    "        # #print(graph_re)\n",
    "        # for i in range(n):\n",
    "        #     graph[i][i] = 0\n",
    "        #     graph_re[i][i] = 0\n",
    "        \n",
    "        # def dijie(n:int,graph_tm:List[List[int]],node:int):\n",
    "        #     dict1 = [float('inf')] * n\n",
    "        #     for i in range(n):\n",
    "        #         dict1[i] = graph_tm[node][i]\n",
    "        #     vis = [0]*n\n",
    "        #     vis[node] = 1\n",
    "        #     for i in range(n-1):\n",
    "        #         mi = float('inf')\n",
    "        #         v = -1\n",
    "        #         for j in range(n):\n",
    "        #             if vis[j] == 0 and dict1[j] < mi:\n",
    "        #                 mi = dict1[j]\n",
    "        #                 v = j\n",
    "        #         vis[v] = 1\n",
    "        #         for j in range(n):\n",
    "        #             if vis[j] == 0 and dict1[v] + graph_tm[v][j] < dict1[j]:\n",
    "        #                 dict1[j] = dict1[v] + graph_tm[v][j]\n",
    "        #     return dict1\n",
    "\n",
    "        # dict1 = dijie(n,graph,src1)\n",
    "        # dict2 = dijie(n,graph,src2)\n",
    "        # dict3 = dijie(n,graph_re,dest)\n",
    "        # #print(graph,'222',graph_re)\n",
    "        # #print(dict1,dict2,dict3)\n",
    "        # mi = float('inf')\n",
    "        # for i in range(n):\n",
    "        #     if dict1[i] != float('inf') and dict2[i] != float('inf') and dict3[i] != float('inf'):\n",
    "        #         if dict1[i]+dict2[i]+dict3[i] < mi:\n",
    "        #             mi = dict1[i]+dict2[i]+dict3[i]\n",
    "        # return mi if mi != float('inf') else -1\n",
    "\n",
    "        g, grev = defaultdict(list), defaultdict(list)\n",
    "        for (x, y, z) in edges:\n",
    "            g[x].append((y, z))\n",
    "            grev[y].append((x, z))\n",
    "        #print(g)\n",
    "        #print(grev)\n",
    "\n",
    "        def dijkstra(graph:Dict[int,List[int]],start:int):\n",
    "            dist = [-1]*n\n",
    "            dist[start] = 0\n",
    "            used = set()\n",
    "            q = [(0,start)]\n",
    "            while q:\n",
    "                u = heapq.heappop(q)[1]\n",
    "                if u in used:\n",
    "                    continue\n",
    "                used.add(u)\n",
    "                for v,w in graph[u]:\n",
    "                    target = dist[u]+w\n",
    "                    if dist[v] == -1 or target < dist[v]:\n",
    "                        dist[v] = target\n",
    "                        heapq.heappush(q,(dist[v],v))\n",
    "            return dist\n",
    "            \n",
    "        dist1 = dijkstra(g,src1)\n",
    "        dist2 = dijkstra(g,src2)\n",
    "        dist3 = dijkstra(grev,dest)\n",
    "            \n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dist1[i] != -1 and dist2[i] != -1 and dist3[i] != -1:\n",
    "                res = dist1[i]+dist2[i]+dist3[i]\n",
    "                if ans == -1 or res < ans:\n",
    "                    ans = res\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        g, grev = defaultdict(list), defaultdict(list)\n",
    "        for (x, y, z) in edges:\n",
    "            g[x].append((y, z))\n",
    "            grev[y].append((x, z)) # 反图\n",
    "        \n",
    "        def dijkstra(graph: Dict[int, List[int]], start: int) -> List[int]:\n",
    "            dist = [-1] * n\n",
    "            dist[start] = 0\n",
    "            used = set()\n",
    "            q = [(0, start)]\n",
    "\n",
    "            while q:\n",
    "                u = heapq.heappop(q)[1]\n",
    "                if u in used:\n",
    "                    continue\n",
    "                \n",
    "                used.add(u)\n",
    "                for (v, weight) in graph[u]:\n",
    "                    target = dist[u] + weight\n",
    "                    if dist[v] == -1 or target < dist[v]:\n",
    "                        dist[v] = target\n",
    "                        heapq.heappush(q, (dist[v], v))\n",
    "            \n",
    "            return dist\n",
    "        \n",
    "        dist1, dist2, dist3 = dijkstra(g, src1), dijkstra(g, src2), dijkstra(grev, dest)\n",
    "        \n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dist1[i] != -1 and dist2[i] != -1 and dist3[i] != -1:\n",
    "                result = dist1[i] + dist2[i] + dist3[i]\n",
    "                if ans == -1 or result < ans:\n",
    "                    ans = result\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        g, grev = defaultdict(list), defaultdict(list)\n",
    "        for (x, y, z) in edges:\n",
    "            g[x].append((y, z))\n",
    "            grev[y].append((x, z))\n",
    "        \n",
    "        def dijkstra(graph: Dict[int, List[int]], start: int) -> List[int]:\n",
    "            dist = [-1] * n\n",
    "            dist[start] = 0\n",
    "            used = set()\n",
    "            q = [(0, start)]\n",
    "\n",
    "            while q:\n",
    "                u = heapq.heappop(q)[1]\n",
    "                if u in used:\n",
    "                    continue\n",
    "                \n",
    "                used.add(u)\n",
    "                for (v, weight) in graph[u]:\n",
    "                    target = dist[u] + weight\n",
    "                    if dist[v] == -1 or target < dist[v]:\n",
    "                        dist[v] = target\n",
    "                        heapq.heappush(q, (dist[v], v))\n",
    "            \n",
    "            return dist\n",
    "        \n",
    "        dist1, dist2, dist3 = dijkstra(g, src1), dijkstra(g, src2), dijkstra(grev, dest)\n",
    "        \n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dist1[i] != -1 and dist2[i] != -1 and dist3[i] != -1:\n",
    "                result = dist1[i] + dist2[i] + dist3[i]\n",
    "                if ans == -1 or result < ans:\n",
    "                    ans = result\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        g, grev = defaultdict(list), defaultdict(list)\n",
    "        for (x, y, z) in edges:\n",
    "            g[x].append((y, z))\n",
    "            grev[y].append((x, z))\n",
    "        \n",
    "        def dijkstra(graph: Dict[int, List[int]], start: int) -> List[int]:\n",
    "            dist = [-1] * n\n",
    "            dist[start] = 0\n",
    "            used = set()\n",
    "            q = [(0, start)]\n",
    "\n",
    "            while q:\n",
    "                u = heapq.heappop(q)[1]\n",
    "                if u in used:\n",
    "                    continue\n",
    "                \n",
    "                used.add(u)\n",
    "                for (v, weight) in graph[u]:\n",
    "                    target = dist[u] + weight\n",
    "                    if dist[v] == -1 or target < dist[v]:\n",
    "                        dist[v] = target\n",
    "                        heapq.heappush(q, (dist[v], v))\n",
    "            \n",
    "            return dist\n",
    "        \n",
    "        dist1, dist2, dist3 = dijkstra(g, src1), dijkstra(g, src2), dijkstra(grev, dest)\n",
    "        \n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if dist1[i] != -1 and dist2[i] != -1 and dist3[i] != -1:\n",
    "                result = dist1[i] + dist2[i] + dist3[i]\n",
    "                if ans == -1 or result < ans:\n",
    "                    ans = result\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "\n",
    "        g = defaultdict(dict)\n",
    "        g2 = defaultdict(dict)\n",
    "        for f, t, w in edges:\n",
    "            if t not in g[f]:\n",
    "                g[f][t] = w\n",
    "            else:\n",
    "                g[f][t] = min(g[f][t], w)\n",
    "            if f not in g2[t]:\n",
    "                g2[t][f] = w\n",
    "            else:\n",
    "                g2[t][f] = min(g2[t][f], w)\n",
    "        \n",
    "        def dijstra(st, g):\n",
    "            dis = [inf] * n\n",
    "            dis[st] = 0\n",
    "            q = [(0, st)]\n",
    "            vis = set()\n",
    "            while q:\n",
    "                d, node = heapq.heappop(q)\n",
    "                if node in vis:\n",
    "                    continue\n",
    "                vis.add(node)\n",
    "                for nei, w in g[node].items():\n",
    "                    if dis[nei] > d + w:\n",
    "                        dis[nei] = d + w\n",
    "                        heapq.heappush(q, (dis[nei], nei))\n",
    "            return dis\n",
    "        d1, d2, d3 = dijstra(src1, g), dijstra(src2, g), dijstra(dest, g2)\n",
    "        ans = inf \n",
    "        for i in range(n):\n",
    "            ans = min(ans, d1[i] + d2[i] + d3[i])\n",
    "\n",
    "        return ans if ans != inf else -1\n",
    "\n",
    "\n",
    "            \n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:\n",
    "        ad={i:[] for i in range(n)}\n",
    "        rd={i:[] for i in range(n)}\n",
    "\n",
    "        for s,e,d in edges:\n",
    "            ad[s].append([e,d])\n",
    "            rd[e].append([s,d])\n",
    "        def dj(g,start):\n",
    "            dis={i:float(\"inf\") for i in range(n)}\n",
    "            dis[start]=0\n",
    "            heap=[]\n",
    "            hq.heappush(heap,[0,start])\n",
    "            visited=set()\n",
    "            while heap:\n",
    "                curd,curn = hq.heappop(heap)\n",
    "                if curn in visited:\n",
    "                    continue\n",
    "                visited.add(curn)\n",
    "                for nexn,nexd in g[curn]:\n",
    "                    newd=curd+nexd\n",
    "                    if dis[nexn] > newd :\n",
    "                        dis[nexn]=newd\n",
    "                        hq.heappush(heap,[newd,nexn])\n",
    "            return dis\n",
    "        \n",
    "        dj1=dj(ad,src1)\n",
    "        dj2=dj(ad,src2)\n",
    "        dj3=dj(rd,dest)\n",
    "        result=-1\n",
    "        ans=float(\"inf\")\n",
    "        for i in range(n):\n",
    "            if dj1[i]!=float(\"inf\") and dj2[i]!=float(\"inf\") and dj3[i]!=float(\"inf\"):\n",
    "                result = dj1[i]+dj2[i]+dj3[i]\n",
    "                ans=min(result,ans)\n",
    "        if ans==float(\"inf\"):\n",
    "            return -1\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
